初始邻接矩阵： [[0 6 13], [10 0 4], [5 ∞ 0]]

Floyd 算法的执行过程 A A(-1) A(0) A(1) A(2) V0 V1 V2 V0 V1 V2 V0 V1 V2 V0 V1 V2 V0 0 6 13 0 6 13 0 6 10 0 6 10 V1 10 0 4 10 0 min(23,4) 10 0 4 9 0 4 V2 5 ∞ 0 5 11 0 5 11 0 5 11 0

c动态数组：

c静态数组：

函数内部两种访问数组的方式都可以：

Floyd 函数

最短路径 遍历所有的组合情况，求出最短的组合方式， 例如比较 d(2,8)+d(4,6)，d(2,6)+d(4,8), d(2,4)+d(6,8), 然后取最小值即为最终的优化方案：d(2,8)+d(4,6)。

求解该步骤的时候，可以使用DFS来寻找最短路径方案，也可以利用DFS的思想，改为动态规划来实现，(状压dp)。 动态规划思路的代码相对没有DFS更符合人们的思路，答题思路是构造一个dp表，行值为1，列值表示该集合中所含的元素，

奇度数数组的所有组合: 2^ods（包括空组合） 例如：集合7表示所含元素在奇度数组中下标为{1, 2, 3}的集合，0、1、2、3、12、13、23、123 e.g.：假设现在得到的奇数度点的数组为：[2，4，6，8]（实际上该数组在后续代码的实现上是[0,2,4,6,8]） 一共有四个有效点，则dp数组应为1×16的规模， dp[0] 表示一个点也没有的集合，空集自然距离也为0， 而更大集合j的最短距离值，应该由更小的集合i及不在i中的两个点x，y求得 e.g.：当求出集合3（{2, 4}）的最短距离时，记录在dp[3]中， 而集合15（{2,4,6,8}）的最短距离可以用dp[3] + d[6][8]来完成更新， 如果dp[3]+d[6][8] // 按位与 : n转换为二进制与1进行按位与运算 (返回奇数度) if (dev[i]&1) { //odds保存奇数度顶点 odds.push_back(i); } } // 查看odds //for(int i=0;i int x = 1; // i= 0,1,2,3. 1&i while ((1 // 10 & 0=0 不执行 if ((1 // N为顶点，R为边 int N,R; cin >> N >> R; // graph初始化为-1，第一行和第一列是空出的。 vector graph(N+1,vector(N+1,-1)); // 度数，初始化为0 vector dev(N+1,0); int res=0; // routes：顶点1和2的距离为3，以此类推。 vector routes={{1,2,3},{2,3,4},{3,4,5},{1,4,10},{1,3,12}}; // 由routes构造邻接矩阵graph for(int i=0;i // cout